
#include "commontools/stdafx.h"
#include "commontools/sparsevector.h"
#include "commontools/myutil.h"

using namespace std;
int zero = 0;

bool checkSame(vector<int> & v, SparseVector<int> osv)
{
	osv.self_check();

	vector<int>t;
	osv.toVector(t);

	SparseVector<int> sv1(zero, t);
	SparseVector<int> sv(zero);

	sv = sv1;

	if(v.size() != sv.size())
	{
		cout << "error 1" << endl;
		return false;
	}
	if(v.empty() != sv.empty())
	{
		return false;
	}

	for(int i = 0; i < v.size(); i++)
	{
		if(v[i] != sv.at(i))
		{
			cout << "error 2" << endl;
			return false;
		}
	}

	if(v.size() > 0 && (!(v.front() == sv.front() && v.back() == sv.back())))
	{
		cout << "error " << __LINE__ << endl;
		return false;
	}
	return true;
}


//sparse vector test，正确性检测

void correct_test()
{
	vector <int> v;
	SparseVector<int> sv(zero);
	srand(time(NULL));
	int runTime = 0;
	while(1)
	{
		int t = rand();
		t = t % 10;

		if(t == 0 || t == 1)
		{
			int x = rand() % 1000 - 500;
			if(x < 800)
			{
				x = zero;
			}
			//cout << "push back  " << x << endl;
			sv.push_back(x);
			v.push_back(x);
		}
		else if(t == 2 || t == 3)
		{
			int pos = rand() % (v.size() + 1);

			int x = rand() % 1000 - 500;
			if(x < 800)
			{
				x = zero;
			}
			//cout << "insert " << pos << "  " << x << endl;
			sv.insert(pos, x);
			v.insert(v.begin() + pos, x);
		}
		else if(t == 4)
		{
			int pos;
			if(v.size() == 0)
			{
				pos = rand() % 2;
			}
			else
			{
				pos = rand() % v.size();
			}

			//cout << "erase " << pos << endl;
			sv.erase(pos);
			if(v.size() != 0)
			{
				v.erase(v.begin() + pos);
			}
			else
			{
				//cout << __LINE__ << endl;
			}
		}
		else if(t == 5)
		{
			int pos;
			if(v.size() == 0)
			{
				pos = rand() % 2;
			}
			else
			{
				pos = rand() % v.size();
			}

			int x = rand() % 1000 - 500;
			if(x < 800)
			{
				x = zero;
			}

			//cout << "set " << pos << " " << x << endl;
			sv.set(pos, x);

			if(v.size() != 0)
			{
				v[pos] = x;
			}
			else
			{
				//cout << __LINE__ << endl;
			}
		}
		else if(t == 6)
		{
			//cout << "pop back" << endl;

			sv.pop_back();

			if(v.size() != 0)
			{
				v.pop_back();
			}
			else
			{
				//cout << __LINE__ << endl;
			}
		}
		else if(t == 7)
		{
			int x = rand() % 1000;
			sv.resize(x);
			v.resize(x, zero);
		}
		else if(t == 8)
		{
			if(v.size() == 0)
			{
				continue;
			}

			int pos = rand() % v.size();
			//cout<<pos<<"  "<<v.size()<<endl;
			int x = rand() % 50 - 25;
			sv.update(pos, x);
			v[pos] += x;
		}
		else if(t == 9)
		{
			if(rand() % 100 < 95)
			{
				continue;
			}
			if(v.size() == 0)
			{
				continue;
			}

			int pos1 = rand() % v.size();
			int pos2 = -1;
			while(pos2 < pos1)
			{
				pos2 = rand() % (v.size() + 1);
			}
			//cout<<pos1<<"  "<<pos2<<endl;
			v.erase(v.begin() + pos1, v.begin() + pos2);
			sv.erase(pos1, pos2);
		}
		else
		{
			cout << "error " << __LINE__ << endl;
			break;
		}

		if(!checkSame(v, sv))
		{
			cout << " error 3" << endl;
			sv.show();
			cout << endl;
			myutil::print(v, 100);

			break;
		}

		if(rand() % 300 == 0)
		{
			sv.clear();
			v.clear();
		}

		runTime++;
		if(runTime % 100000 == 0)
		{
			cout << runTime << " ";
			for(int x = 0; x < runTime / 1000000; x++)
			{
				cout << "=";
			}
			cout << endl;
		}
		if(runTime > 1e6)
		{
			break;
		}
	}
}


int main(int argc, char * argv[])
{
	//system("dir");

	cout << "endl" << endl;

	myutil::pause(12);
	while(1)
	{
		srand(time(NULL));
		zero = rand() % 100 - 50;
		if(zero % 4 == 0)
		{
			zero = 0;
		}
		cout << "z: " << zero << endl;
		correct_test();
	}
	SparseVector<int> v(0);

	v.push_back(3);
	v.push_back(8);

	cout << v.size() << endl;
	cout << v.at(0) << endl;

	cout << v.at(0) << endl;

	cout << "hello" << endl;
	cout << "h" << endl;
	return 0;
}
